package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.Scanner;

/*
输入正整数n，对1-n进行排列，使得相邻两个数之和均为素数，
输出时从整数1开始，逆时针排列。同一个环应恰好输出一次。
n <= 16

如输入：6
输出：
1 4 3 2 5 6
1 6 5 2 3 4
*/
public class hDFS_素数环 {
	public static void main(String[] args) {
		hDFS_素数环 test = new hDFS_素数环();
		test.useDFS_PrimeRing();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS_PrimeRing() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] recall = new int[n];
		recall[0] = 1;//默认环开始从1开始；其实你从什么数开始都无所谓，因为是环。
		DFS_PrimeRing(recall, 1, n);//因为索引0的元素是1，那么就从索引1开始
	}
	
	/**
	 * 递归形式
	 * @param recall
	 * @param current
	 * @param n
	 */
	public void DFS_PrimeRing(int[] recall, int current, int n) {
		if (current == n && isPrimeNumber(recall[0] + recall[n - 1])) {//出口；索引current(=n)已经越界，同时最后一个元素recall[n -1]与第一个元素recall[0]的和确实是素数
			print(recall);//输出环
			return;//结束这条深搜递归
		}
		for (int number = 2; number <= n; number++) {//从数字2开始，到数字n结束；深度递归
			if (check(recall, current, number)) {//剪枝
				recall[current] = number;
				DFS_PrimeRing(recall, current + 1, n);//深度递归尝试
				recall[current] = 0;//回溯
			}
		}
	}
	
	/**
	 * 剪枝核心语句
	 * @param recall
	 * @param current
	 * @param number
	 * @return
	 */
	public boolean check(int[] recall, int current, int number) {
		for (int element : recall) {//对已存入环内的元素
			if (element == number) {////如果元素==新尝试的数字number,那么不通过
				return false;
			}
			if (!isPrimeNumber(number + recall[current - 1])) {//如果当前位置的数字recall[current]（就是新尝试的数字number） + 前一个数字recall[current - 1]不是素数，那么不通过
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 判断素数
	 * @param number
	 * @return
	 */
	public boolean isPrimeNumber(int number) {
		for (int i = 2; i * i <= number; i++) {
			if (number % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 打印环
	 * @param recall
	 */
	public void print(int[] recall) {
		for (int i = 0; i < recall.length; i++) {
			if (i == recall.length - 1) {
				System.out.println(recall[i]);
			} else {
				System.out.print(recall[i] + " ");
			}
		}
	}
}
